#ifndef SORT_H__
#define SORT_H__

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdbool.h>
#ifdef __cplusplus
extern "C" {
#endif



// 不建议使用偏移方法, 不知道对于不连续的内存会如何
// 由于不知道sort_data_in的类型, 为了利用它的类型, 将temp作为sort_data_in的元素
// 由于temp肯定不在sort_data_in内, 因此要计算偏移
// 算出来的偏移不一定正好四字节对齐, 因此temp预留大一些, 保证落入temp区域
// 最好让输入数据四字节对齐, 赋值效率较高

// #undef __GNUC__

#define SORT_PRINTF(...)

// BUB_SORT
// SEL_SORT
// INS_SORT
// SHELL_SORT
#define SORT_DATA   BUB_SORT    // 选择要测试的排序算法

#ifndef __GNUC__
#if defined(INS_SORT) || defined(SHELL_SORT)
static unsigned char swap_temp[16];
#endif
#endif // __GNUC__

static inline int32_t calc_offset(void *in, void *temp, int32_t size)
{
    int32_t offset = (int32_t)temp - (int32_t)in;
    offset = (offset / size) + 1;   // 保证落入temp区域内
    return offset;
}


#ifndef __GNUC__
#define SORT_SWAP(a, b)  \
do{     \
    unsigned char temp[8];              \
    memcpy(temp, &a, sizeof(a));  \
    memcpy(&a, &b, sizeof(a));  \
    memcpy(&b, temp, sizeof(a));  \
    (void) ( &a == &b );    \
}while(0)


#else
#define SORT_SWAP(a, b)  \
do{                                                 \
    __typeof(a)  temp;               \
    temp = a;   \
    a = b;      \
    b = temp;   \
    (void) ( &a == &b );  \
}while(0)
#endif // __GNUC__




#define SEL_SORT(sort_data_in, len)                              \
do{                                             \
    SORT_PRINTF("sel_sort\n ");                  \
    int i, j;                               \
    for ( i = 0; i < len - 1; i++ ){            \
        int min = i;                                \
        for (j = i + 1; j < len; j++){    \
            if ( sort_data_in[j] < sort_data_in[min] ) {        \
                min = j;                                         \
            }                                   \
        }                                       \
        SORT_SWAP(sort_data_in[min], sort_data_in[i]);                                 \
    }                                           \
                                                \
}while(0)


#define BUB_SORT(sort_data_in, len)                                 \
do{                                             \
    SORT_PRINTF("bub_sort\n ");                  \
    int i, j;                               \
    for ( i = 0; i < len - 1; i++ ){            \
        for ( j = 0; j < len - 1 - i; j++ ){    \
            if ( sort_data_in[j] > sort_data_in[j + 1] ) {      \
                SORT_SWAP(sort_data_in[j], sort_data_in[j + 1]);                         \
            }                                   \
        }                                       \
    }                                           \
}while(0)


#ifndef __GNUC__
#define INS_SORT(sort_data_in, len)                              \
do{                                             \
    SORT_PRINTF("ins_sort general\n ");                  \
    int i, j;                               \
    int32_t offset = calc_offset(sort_data_in, swap_temp, sizeof(sort_data_in[0]) );  \
    for ( i = 1; i < len; i++ ){            \
        sort_data_in[offset] = sort_data_in[i];                      \
        for (j = i; j > 0 && sort_data_in[j - 1] > sort_data_in[offset]; j--){              \
            sort_data_in[j] = sort_data_in[j - 1];              \
        }       \
        sort_data_in[j] = sort_data_in[offset];  \
    }                                           \
}while(0)
#else
// 用到了typeof, 必须为gnu或开启gnu扩展的其他编译器
#define INS_SORT(sort_data_in, len)                              \
do{                                             \
    SORT_PRINTF("ins_sort gnu\n ");                  \
    int i, j;                               \
    __typeof__(sort_data_in[0])     temp;   \
    for ( i = 1; i < len; i++ ){            \
        temp = sort_data_in[i];                      \
        for (j = i; j > 0 && sort_data_in[j - 1] > temp; j--){              \
            sort_data_in[j] = sort_data_in[j - 1];              \
        }       \
        sort_data_in[j] = temp;  \
    }                                           \
}while(0)

#endif // __GNUC__

#ifndef __GNUC__

#define SHELL_SORT(sort_data_in, len)                               \
do{                                             \
    SORT_PRINTF("shell_sort gereral\n ");                  \
    int gap, i, j;                              \
    int32_t offset = calc_offset(sort_data_in, swap_temp, sizeof(sort_data_in[0]) );  \
    for (gap = len >> 1; gap > 0; gap = gap >> 1){  \
        for (i = gap; i < len; i++) {                               \
            sort_data_in[offset] = arr[i];                                          \
            for (j = i - gap; j >= 0 && arr[j] > sort_data_in[offset]; j -= gap){   \
                arr[j + gap] = arr[j];                              \
            }                                                       \
            arr[j + gap] = sort_data_in[offset];                                    \
        }                                                           \
    }                                            \
}while(0)

#else

#define SHELL_SORT(sort_data_in, len)                               \
do{                                             \
    SORT_PRINTF("shell_sort gnu\n ");                  \
    int gap, i, j;                              \
    __typeof__(sort_data_in[0])     temp;       \
    for (gap = len >> 1; gap > 0; gap = gap >> 1){  \
        for (i = gap; i < len; i++) {                               \
            temp = sort_data_in[i];                                          \
            for (j = i - gap; j >= 0 && sort_data_in[j] > temp; j -= gap){   \
                sort_data_in[j + gap] = sort_data_in[j];                              \
            }                                                       \
            sort_data_in[j + gap] = temp;                                    \
        }                                                           \
    }                                            \
}while(0)

#endif


//================================== qsort =========================================
typedef unsigned long  my_sort_ulong;
typedef int (*qsort_cmp_type)(const void * a, const void * b);
qsort_cmp_type  get_user_cmp_handler(void);
void set_user_cmp_handler(qsort_cmp_type    p_func);

#if (__STDC_VERSION__ >= 201103L)
#define get_ascend_func(x, type) _Generic((x), \
    char:       cmp_##type##_char, \
    int8_t:     cmp_##type##_int8_t, \
    uint8_t:    cmp_##type##_uint8_t, \
    int16_t:    cmp_##type##_int16_t, \
    uint16_t:   cmp_##type##_uint16_t, \
    int32_t:    cmp_##type##_int32_t, \
    uint32_t:   cmp_##type##_uint32_t, \
    long:       cmp_##type##_long,    \
    my_sort_ulong:      cmp_##type##_my_sort_ulong,    \
    int64_t:    cmp_##type##_int64_t, \
    uint64_t:   cmp_##type##_uint64_t, \
    float:      cmp_##type##_float, \
    double:     cmp_##type##_double,    \
    default:    get_user_cmp_handler() )
#else
#ifdef __cplusplus
#define IS_SAME_TYPE(T1, T2)    std::is_same<T1, T2>::value

#else
#define IS_SAME_TYPE(T1, T2)    __builtin_types_compatible_p(T1, T2)
#endif
#define     get_ascend_func(x, type)    ({      \
    qsort_cmp_type     cmp_handler = (qsort_cmp_type)0;   \
    if ( IS_SAME_TYPE(__typeof(x), char) ){      \
        cmp_handler = cmp_##type##_char;                          \
    }else if ( IS_SAME_TYPE(__typeof(x), int8_t) ){      \
        cmp_handler = cmp_##type##_int8_t;                        \
    }else if ( IS_SAME_TYPE(__typeof(x), uint8_t) ){      \
        cmp_handler = cmp_##type##_uint8_t;                        \
    }else if ( IS_SAME_TYPE(__typeof(x), int16_t) ){     \
        cmp_handler = cmp_##type##_int16_t;                         \
    }else if ( IS_SAME_TYPE(__typeof(x), uint16_t) ){     \
        cmp_handler = cmp_##type##_uint16_t;                       \
    }else if ( IS_SAME_TYPE(__typeof(x), int32_t) ){        \
        cmp_handler = cmp_##type##_int32_t;                           \
    }else if ( IS_SAME_TYPE(__typeof(x), uint32_t) ){         \
        cmp_handler = cmp_##type##_uint32_t;                          \
    }else if ( IS_SAME_TYPE(__typeof(x), float ) ){                    \
        cmp_handler = cmp_##type##_float;                         \
    }else if ( IS_SAME_TYPE(__typeof(x), long ) ){                    \
        cmp_handler = cmp_##type##_long;                         \
    }else if ( IS_SAME_TYPE(__typeof(x), my_sort_ulong ) ){                    \
        cmp_handler = cmp_##type##_my_sort_ulong;                         \
    }else if ( IS_SAME_TYPE(__typeof(x), int64_t ) ){                    \
        cmp_handler = cmp_##type##_int64_t;                         \
    }else if ( IS_SAME_TYPE(__typeof(x), uint64_t ) ){                    \
        cmp_handler = cmp_##type##_uint64_t;                         \
    }else if ( IS_SAME_TYPE(__typeof(x), double) ){          \
        cmp_handler = cmp_##type##_double;                             \
    }else{                                                  \
        cmp_handler = get_user_cmp_handler();   \
    }   \
    cmp_handler;    \
})
#endif


// 升序排列
#define QSORT_ASCEND(base, nitems) \
do{         \
    qsort(base, nitems, sizeof(base[0]), get_ascend_func(base[0], ascend) );\
}while(0)

// 降序排列
#define QSORT_DESCEND(base, nitems) \
do{         \
    qsort(base, nitems, sizeof(base[0]), get_ascend_func(base[0], descend) );\
}while(0)



#define L_GREATER_THAN_R(x, y)      (x > y ? 1 : -1)
#define L_LESS_THAN_R(x, y)         (x < y ? 1 : -1)

#define DEFINE_CMP(type)    \
int cmp_ascend_##type(const void * a, const void * b)    \
{   \
    return L_GREATER_THAN_R( *(type*)a , *(type*)b );   \
}   \
int cmp_descend_##type(const void * a, const void * b)    \
{   \
    return L_LESS_THAN_R( *(type*)a , *(type*)b );   \
}   \


#define DECLARE_CMP(type)   \
int cmp_ascend_##type(const void * a, const void * b);  \
int cmp_descend_##type(const void * a, const void * b);

DECLARE_CMP(char)
DECLARE_CMP(int8_t)
DECLARE_CMP(uint8_t)
DECLARE_CMP(int16_t)
DECLARE_CMP(uint16_t)
DECLARE_CMP(int32_t)
DECLARE_CMP(uint32_t)
DECLARE_CMP(long)
DECLARE_CMP(my_sort_ulong)
DECLARE_CMP(int64_t)
DECLARE_CMP(uint64_t)
DECLARE_CMP(float)
DECLARE_CMP(double)


#define sort(first, last, ...)   \
({  \
    STATIC_ASSERT(types_cmp_p(__typeof(first), __typeof(last) ), "file:" __FILE__ " line:" TO_STRING(__LINE__) " must be same type" ); \
    size_t width = sizeof(*first);  \
    size_t nelem = (size_t)(last - first); \
    if(MY_NUM_VA_ARGS(__VA_ARGS__) == 0){   \
        qsort(first, nelem, width, get_ascend_func(*first, ascend) );   \
    }else{  \
        qsort(first, nelem, width, GET_ARGS(__VA_ARGS__) + 0 );   \
    }   \
})

void bub_sort(void *first, size_t nelem, size_t width, qsort_cmp_type   cmp);
#define stable_sort(first, last, ...)    \
({  \
    STATIC_ASSERT(types_cmp_p(__typeof(first), __typeof(last) ), "file:" __FILE__ " line:" TO_STRING(__LINE__) " must be same type" ); \
    size_t width = sizeof(*first);  \
    size_t nelem = (size_t)(last - first); \
    if(MY_NUM_VA_ARGS(__VA_ARGS__) == 0){   \
        bub_sort(first, nelem, width, get_ascend_func(*first, ascend) ); \
    }else{  \
        bub_sort(first, nelem, width, GET_ARGS(__VA_ARGS__) + 0 ); \
    }   \
})

typedef bool (*is_sorted_cmp_t)(void *a, void *b);
bool is_sorted_$(void *first, void *last, size_t width, is_sorted_cmp_t     cmp);
#define is_sorted(first, last, ...) \
({  \
    STATIC_ASSERT(types_cmp_p(__typeof(first), __typeof(last) ), "file:" __FILE__ " line:" TO_STRING(__LINE__) " must be same type" ); \
    size_t width = sizeof(*first);  \
    bool     res_in_is_sorted;   \
    if(MY_NUM_VA_ARGS(__VA_ARGS__) == 0){   \
        res_in_is_sorted = is_sorted_$(first, last, width, get_is_sorted_func(*first) ); \
    }else{  \
        res_in_is_sorted = is_sorted_$(first, last, width, (is_sorted_cmp_t)(GET_ARGS(__VA_ARGS__) + 0) ); \
    }   \
    res_in_is_sorted;   \
})

#define get_is_sorted_func(x) _Generic((x), \
    char:       cmp_is_sorted_char, \
    int8_t:     cmp_is_sorted_int8_t, \
    uint8_t:    cmp_is_sorted_uint8_t, \
    int16_t:    cmp_is_sorted_int16_t, \
    uint16_t:   cmp_is_sorted_uint16_t, \
    int32_t:    cmp_is_sorted_int32_t, \
    uint32_t:   cmp_is_sorted_uint32_t, \
    long:       cmp_is_sorted_long,    \
    unsigned long:      cmp_is_sorted_uint32_t,    \
    int64_t:    cmp_is_sorted_int64_t, \
    uint64_t:   cmp_is_sorted_uint64_t, \
    default:    NULL )

#define DECLARE_IS_SORTED_CMP(type)   \
bool cmp_is_sorted_##type(void * a, void * b);

DECLARE_IS_SORTED_CMP(char)
DECLARE_IS_SORTED_CMP(int8_t)
DECLARE_IS_SORTED_CMP(uint8_t)
DECLARE_IS_SORTED_CMP(int16_t)
DECLARE_IS_SORTED_CMP(uint16_t)
DECLARE_IS_SORTED_CMP(int32_t)
DECLARE_IS_SORTED_CMP(uint32_t)
DECLARE_IS_SORTED_CMP(long)
DECLARE_IS_SORTED_CMP(int64_t)
DECLARE_IS_SORTED_CMP(uint64_t)
DECLARE_IS_SORTED_CMP(float)
DECLARE_IS_SORTED_CMP(double)

#ifdef __cplusplus
}
#endif

#endif // SORT_H__
